Various applications may be modeled as network problems. For example, applications in different disciplines including geographic information systems, social sciences, life sciences, and so on, may be modeled as network problems. Different conventional tools can be used to analyze networks and network problems. These tools use two conventional approaches for network analysis. Both of these conventional approaches may have issues that lead to certain limitations. For example, a first conventional approach involves pre-loading an entire network into memory before analyzing the network. This approach may suffer and even fail if the amount of data describing the network exceeds the available memory capacity.
A second conventional approach involves pre-computing all possible analysis results for a network and then storing the analysis results. Later arriving analysis requests are then satisfied by consulting the pre-computed data. However, this approach is time consuming and impractical for large networks. This approach is particularly impractical for large dynamic networks. To provide up-to-date results, a network must be constantly monitored and the pre-computed results re-computed upon detecting any change in the network.
A network is a graph representation for modeling objects of interest and their relationships. A network has nodes, links, and paths. A node may model an object of interest. A link may model a relationship between two nodes. A path may model an ordered list of connected links. Data structures may be populated with data associated with nodes, links, and paths. Thus, a network may be associated with a network data model. A data model may include, for example, network metadata, a node table, a link table, a path table, and so on. In one conventional approach, before any network analysis is performed, all this data must be loaded into memory.
A network model may also provide analysis functions. For example, a network model may provide a shortest path function, an all paths function, a connected components function, a within-cost function, a nearest-neighbor function, a minimum cost spanning tree function, and so on. In one conventional approach, results for these functions may be pre-computed and stored to satisfy later arriving analysis requests. However, if the network has changed between the time the results were computed and the time the request arrives, then the results will be out-of-date and may have to be recomputed.